The edit distance problem is to find the minimum cost of edit operations to transform one string to the other. Wu presented an algorithm for edit distance problem with with that the cost of an insertion or deletion is 1 and the cost of a replacement is 2. This algorithm performs well when the two strings are similar. the ideal of the algorithm is similar to Myers's algorithm. Wu et al. reduced the search range of diagonals from the algorithm of Myers. This algorithm determine the edit distance in O(n*p) time, where p is the number of deletions in the edit operations.
int Wu_Alg(char *A, char *B, int m, int n)
{
int *realfp = new int[m+n+3];
int *fp, p, delta;
fp = realfp + n + 1;
memset(realfp, -1, (m+n+2)*sizeof(int));
delta = n - m;
p = -1;
while(fp[delta] != n){
p=p+1;
for(int k = -p; k <= delta-1; k++){
fp[k]=snake(A, B, m, n, k, Max(fp[k-1]+1, fp[k+1]));
}
for(int k = delta+p; k >= delta+1; k--){
fp[k] = snake(A, B, m, n, k, Max(fp[k-1]+1, fp[k+1]));
}
fp[delta] = snake(A, B, m, n, delta, Max(fp[delta-1]+1, fp[delta+1]));
}
delete [] realfp;
return delta+2*p;
}
int snake(char *A, char *B, int m, int n, int k, int j)
{
int i=j-k;
while(i < m && j < n && A[i+1] == B[j+1]){
i++;
j++;
}
return j;
}